package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/subsets/'>子集(Subsets)</a>
 * <p>给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。【数组的 子集 是从数组中选择一些元素（可能为空）。】</p>
 * <p>解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,2,3]
 *      输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 *
 * 示例 2：
 *      输入：nums = [0]
 *      输出：[[],[0]]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= nums.length <= 10</li>
 *         <li>-10 <= nums[i] <= 10</li>
 *         <li>nums 中的所有元素 互不相同</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0078Subsets_M 子集(Subsets)
 * @see LC0090Subsets_II_M 子集II(Subsets II)
 * @since 2025/2/14 10:31
 */
public class LC0078Subsets_M {
    static class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> resList = new ArrayList<>();
            // 1.先不选，加到结果集中；
            // 2.再选择，加到结果集中，后回溯
            backtracking1(nums, 0, new ArrayList<>(), resList);
            // 对于数组中的任何一个值，都有两种情况：
            // 1.选择当前值
            // 2.不选择当前值
            //backtracking2(nums, 0, new ArrayList<>(), resList);
            return resList;
        }

        private void backtracking1(int[] nums, int startIdx, List<Integer> path, List<List<Integer>> resList) {
            resList.add(new ArrayList<>(path));
            for (int i = startIdx; i < nums.length; i++) {
                path.add(nums[i]);
                backtracking1(nums, i + 1, path, resList);
                path.remove(path.size() - 1);
            }
        }

        private void backtracking2(int[] nums, int currIdx, List<Integer> path, List<List<Integer>> resList) {
            if (currIdx == nums.length) {
                resList.add(new ArrayList<>(path));
                return;
            }
            // 1.选择当前值
            path.add(nums[currIdx]);                // 处理
            backtracking2(nums, currIdx + 1, path, resList);    // 递归
            path.remove(path.size() - 1);     // 回溯

            // 2.不选择当前值
            backtracking2(nums, currIdx + 1, path, resList);    // 递归
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListListInteger(solution.subsets(new int[]{1, 2, 3}));
        Printer.printListListInteger(solution.subsets(new int[]{0}));
    }
}
